#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include "fib_heap.h"

FH *make_fib_heap() {
	FH *H=(FH*)malloc(sizeof(FH));
	if(H==NULL)
		return NULL;
	H->n=0;
	H->min=NULL;
	return H;
}

FHE *make_fib_heap_elem(int key) {
	FHE *HE=(FHE*)malloc(sizeof(FHE));
	if(HE==NULL)
		return NULL;
	HE->key=key;
	HE->degree=0;
	HE->marked=0;
	HE->left=HE->right=HE;
	HE->parent=HE->child=NULL;
	return HE;
}

void fib_heap_insert(FH **H,FHE **x) {
	if((*H)->min==NULL) {
		(*x)->left=(*x)->right=*x;
		(*H)->min=*x;
	} else {
		(*x)->left=(*H)->min->left;
		(*x)->left->right=(*x);
		(*x)->right=(*H)->min;
		(*x)->right->left=(*x);
		if((*x)->key<(*H)->min->key)
			(*H)->min=*x;
	}
	(*H)->n+=1;
}

FHE *find_min(FH *H) {
	if(H==NULL)
		return NULL;
	else
		return H->min;
}

FH *fib_heap_union(FH* H1,FH* H2) {
	if(H1->min==NULL || H2->min==NULL)
		return NULL;
	FH *H=make_fib_heap();
	H->min=H1->min;

	/*concatenate root list of H2 to root list of H*/{
		FHE *temp=H2->min->left;
		H2->min->left=H->min->left;
		H2->min->left->right=H2->min;
		H->min->left=temp;
		H->min->left->right=H->min;
	}
	if(H1->min->key>H2->min->key)
		H->min=H2->min;
	H->n=H1->n+H2->n;
	return H;
}

void fib_heap_link(FH **H,FHE **y,FHE **x) {
	(*y)->right->left=(*y)->left;
	(*y)->left->right=(*y)->right;
	if(*y==(*H)->min)
		(*H)->min=(*H)->min->right;
	if((*x)->child==NULL) {
		(*x)->child=*y;
		(*y)->left=(*y)->right=*y;
		(*y)->parent=(*x);
	} else {
		(*y)->left=(*x)->child->left;
		(*y)->left->right=(*y);
		(*y)->right=(*x)->child;
		(*y)->right->left=(*y);
		(*y)->parent=(*x);
	}
	(*x)->degree++;
	(*y)->marked=0;
}

int upper_bound(FH* H) {
	double phi=(1+sqrt(5.00))/2;
	double log_phi_n=(log10((double)H->n))/(log10(phi));
	return floorl(log_phi_n);
}

void consolidate(FH** H) {
	int i,d;
	FHE **A=(FHE**)malloc(upper_bound(*H)*sizeof(FHE*));
	if(A==NULL)
		return;
	for(i=0;i<upper_bound(*H);i++)
		A[i]=NULL;
	FHE *W,*X,*Y,*TEMP;
	while((W=(*H)->min)!=NULL) {
		X=W;
		W->left->right=W->right;
		W->right->left=W->left;
		if(W==W->left)
			(*H)->min=NULL;
		else
			(*H)->min=W->right;
		if(W->parent!=NULL && W->parent->child==W)
			W->parent->child=W->right;
		W->parent=NULL;
		W->left=W->right=W;
		d=X->degree;
		while(A[d]!=NULL) {
			Y=A[d];
			if(X->key>Y->key) {
				TEMP=Y;
				Y=X;
				X=TEMP;
			}
				fib_heap_link(&*H,&Y,&X);
			A[d]=NULL;
			d++;
		}
		A[d]=X;
	}
	(*H)->min=NULL;
	for(i=0;i<upper_bound(*H);i++) {
		if(A[i]!=NULL) {
			fib_heap_insert(&*H,&A[i]);
			(*H)->n--;
			if((*H)->min==NULL || (*H)->min->key>A[i]->key)
				(*H)->min=NULL;
		}
	}
	free(A);
}

FHE *fib_heap_extract_min(FH **H) {
	FHE *Z=(*H)->min,*X;
	if(Z!=NULL) {
		set_as_child_helper(&*H,&Z);
		//remove Z from root list of H
		if(Z==Z->right)
			(*H)->min=NULL;
		else {
			(*H)->min=Z->right;
			if(Z->left)
				Z->left->right=Z->right;
			if(Z->right)
				Z->right->left=Z->left;
		}
		consolidate(&*H);
		(*H)->n--;
	}
	return Z;
}


void set_as_child_helper(FH **H,FHE **E) {
	if((*E)->degree==0||*E==NULL||*H==NULL)
		return;
	while(1) {
		if((*E)->degree==0) {
			(*E)->child=NULL;
			break;
		}
		FHE *temp=(*E)->child;
		(*E)->child=temp->left;
		(*E)->child->left->right=(*E)->child;
		(*E)->child->right->left=(*E)->child;
		temp->parent=NULL;
		fib_heap_insert(&*H,&temp);
		(*H)->n--;
		(*E)->degree--;
	}
}

void cut(FH **H,FHE **X,FHE **Y) {
	(*X)->left->right=(*X)->right;
	(*X)->right->left=(*X)->left;
	if(*X==(*X)->right)
		if((*X)->parent!=NULL && (*X)->parent->child==*X)
			(*X)->parent->child=NULL;
	else {
		if((*X)->parent!=NULL && (*X)->parent->child==(*X))
			(*X)->parent->child=(*X)->right;
	}
	(*Y)->degree--;
	if((*H)->min==NULL) {
		(*X)->left=(*X)->right=*X;
		(*H)->min=*X;
	} else {
		(*X)->left=(*H)->min->left;
		(*X)->left->right=(*X);
		(*X)->right=(*H)->min;
		(*X)->right->left=(*X);
		if((*X)->key<(*H)->min->key)
			(*H)->min=*X;
	}
	(*X)->parent=NULL;
	(*X)->marked=0;
}

void cascading_cut(FH **H,FHE **Y) {
	FHE *Z;

	while((Z=(*Y)->parent)!=NULL) {
		if((*Y)->marked==0) {
			(*Y)->marked=1;
			return;
		} else {
			cut(&*H,&*Y,&Z);
			*Y=Z;
		}
	}
}

void fib_heap_decrease_key(FH **H,FHE **X,int k) {
	if(k>(*X)->key) {
		return;
	}
	(*X)->key=k;
	FHE *Y=(*X)->parent;
	if(Y!=NULL && (*X)->key<Y->key) {
		cut(&*H,&*X,&Y);
		cascading_cut(&*H,&Y);
	}
	if((*X)->key<(*H)->min->key)
		(*H)->min=*X;
}

void fib_heap_delete(FH **H,FHE **X) {
	fib_heap_decrease_key(&*H,&*X,INT_MIN);
	FHE *Z=fib_heap_extract_min(&*H);
	free(Z);
}